package 搜索算法;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 *
 */
@SuppressWarnings("all")
public class 迷路的机器人 {
    public static void main(String[] args) {
        int[][] a = {{0,0,0},{0,1,0},{0,0,0}};
        pathWithObstacles(a);
    }

    public static List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        // 题目规定只能向下或者向右移动
        int[] dx = {0,1}; // 定义x方向的偏移数组
        int[] dy = {1,0}; // 定义y方向的偏移数组
        int x = 0; int y = 0; // 定义初始位置
        int d = 0; // 定义初始方向
        int row = obstacleGrid.length; // 行数
        int col = obstacleGrid[0].length; // 列数
        List<List<Integer>> path = new ArrayList<>(); // 记录路径
        List<Integer> init = new ArrayList<>();
        init.add(0);
        init.add(0);
        path.add(init);
        boolean[][] visited = new boolean[row][col];
        // 程序结束的标志：x = row - 1; y = col - 1; 即移动到右下角的位置，找到出口
        while(x != row - 1 && y != col - 1) {
            int a = x + dx[d];
            int b = y + dy[d];
            if(a >= row || b >= col || visited[a][b] == true) {
                // 需要换方向
                d = (d + 1) % 2;
                a = x + dx[d];
                b = y + dy[d];
                x = a;
                y = b;
            } else {
                List<Integer> temp = new ArrayList<>();
                temp.add(a);
                temp.add(b);
                path.add(temp);
            }
        }
        return path;
    }
}
